Online and other remote data storage services have become widely available in recent years. In a typical model, a storage service may provide storage for backup data, which may be retrieved in the event of a hardware failure, an accidental deletion of data, or data loss as a result of a security breach or other malicious act. Storage services may also provide long-term remote storage for archival or historical purposes. Some storage services, and their underlying storage systems, support the storing of multiple versions of a file or other stored data for simple backup and recovery services, but they typically do not support access to, and/or control over, multiple versions of a file or other stored data.
The term “tombstone” is sometimes used to refer to an entity that represents a deletion of stored data. Tombstones are sometimes used in distributed storage systems to ensure that deletions are performed consistently across separate data store instances. For example, when an anti-entropy process is reconciling two separate data store instances, the existence of a tombstone in the up-to-date data store may trigger the creation of an analogous tombstone in the out-of-date data store. Without such a tombstone, a deletion of a data element in the up-to-date data store could be reconciled away due to the existence of the data element in the out-of-date data store. The typical process for tombstone deletion in distributed systems involves a tombstone time-to-live (TTL), whose value may be chosen based upon the expected time for a successful round of the system anti-entropy protocol to execute.
While the technology described herein is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the disclosure to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present disclosure as defined by the appended claims.